package org.skiplist2;



import java.util.Collection;
import java.util.Comparator;
import java.util.Random;

public class SkipList<E> extends AbstractSkipList<E> {

    private int topLevel = 0;

    private int size = 0;

    private Node<E> head;

    private Random random;

    private final Comparator<? super E> comparator;

    public SkipList() {
        this(null);
    }

    public SkipList(Comparator<? super E> c) {
        head = new Node<>(null, 3);
        this.comparator = c;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    @Override
    public boolean contains(E e) {
        return find(e) != null;
    }

    @Override
    public boolean add(E e) {
        if (e == null) {
            throw new NullPointerException();
        }

        int level = randomLevel();
        Node<E> newNode;
        if (level > topLevel) {
            topLevel++;
            resize();
            newNode = new Node<>(e, topLevel);
        } else {
            newNode = new Node<>(e, level);
        }
        Node<E>[] preNodes = getPreNodes(e, newNode.getLevel());
        for (int i = 0; i < preNodes.length; i++) {
            Node<E> pre = preNodes[i];
            newNode.setNextNode(i, pre.getNextNode(i));
            pre.setNextNode(i, newNode);
        }
        size++;
        return true;
    }

    @Override
    public boolean remove(E e) {
        Node<E> del = find(e);
        if (del == null) {
            return false;
        }
        Node<E>[] preNodes = getPreNodes(e, del.getLevel());
        for (int i = 0; i < preNodes.length; i++) {
            Node<E> pre = preNodes[i];
            pre.setNextNode(i, del.getNextNode(i));
            del.setNextNode(i, null);
        }
        while (topLevel > 0) {
            if (head.getNextNode(topLevel) == null) {
                topLevel--;
            } else {
                break;
            }
        }
        size--;
        return true;
    }

    @Override
    public void clear() {
        for (int i = 0; i <= topLevel; i++) {
            head.setNextNode(i, null);
        }
        topLevel = 0;
        size = 0;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c) {
            if (add(e)) modified = true;
        }
        return modified;
    }

    @Override
    public E first() {
        if (head.getNextNode(0) != null) {
            return head.getNextNode(0).getValue();
        }
        return null;
    }

    @Override
    public E last() {
        Node<E> temp = head;
        for (int i = topLevel; i >= 0; i--) {
            while (temp.getNextNode(i) != null) {
                temp = temp.getNextNode(i);
            }
        }
        return temp.getValue();
    }

    @Override
    public String toString() {
        if (isEmpty()) return "[]";

        StringBuilder b = new StringBuilder();
        b.append('[');

        Node temp = head;
        while (temp.getNextNode(0) != null) {
            b.append(temp.getNextNode(0).getValue());
            temp = temp.getNextNode(0);
            if (temp.getNextNode(0) == null) {
                b.append(']');
                break;
            }
            b.append(", ");
        }
        return b.toString();
    }

    private int randomLevel() {
        if (random == null) {
            random = new Random();
        }
        int level = 0;
        int times = topLevel + 1;
        while (times-- > 0) {
            if (!random.nextBoolean()) {
                break;
            }
            level++;
        }
        return level;
    }

    private Node<E>[] getPreNodes(E e, int level) {
        if (e == null) {
            return null;
        }
        Node<E>[] preNodes = new Node[level + 1];
        Node<E> temp = head;
        Comparator<? super E> cpr = comparator;
        Node<E> next;
        if (cpr != null) {
            for (int i = topLevel; i >= 0; i--) {
                while ((next = temp.getNextNode(i)) != null && cpr.compare(next.getValue(), e) < 0) {
                    temp = next;
                }
                if (i <= level) {
                    preNodes[i] = temp;
                }
            }
        } else {
            for (int i = topLevel; i >= 0; i--) {
                while ((next = temp.getNextNode(i)) != null && ((Comparable<? super E>) next.getValue()).compareTo(e) < 0) {
                    temp = next;
                }
                if (i <= level) {
                    preNodes[i] = temp;
                }
            }
        }
        return preNodes;
    }

    private void resize() {
        if (topLevel > head.getLevel()) {
            Node<E> newHead = new Node(null, topLevel);
            for (int i = 0; i <= head.getLevel(); i++) {
                newHead.setNextNode(i, head.getNextNode(i));
                head.setNextNode(i, null);
            }
            head = newHead;
        }
    }

    private Node<E> find(E e) {
        if (e == null) {
            throw new NullPointerException();
        }
        Node<E> temp = head;
        for (int i = topLevel; i >= 0; i--) {
            if (comparator != null) {
                while (temp.getNextNode(i) != null) {
                    int c = comparator.compare(temp.getNextNode(i).getValue(), e);
                    if (c < 0) {
                        temp = temp.getNextNode(i);
                    } else if (c == 0) {
                        return temp.getNextNode(i);
                    } else {
                        break;
                    }
                }
            } else {
                while (temp.getNextNode(i) != null) {
                    Comparable<? super E> v = (Comparable<? super E>) temp.getNextNode(i).getValue();
                    int c = v.compareTo(e);
                    if (c < 0) {
                        temp = temp.getNextNode(i);
                    } else if (c == 0) {
                        return temp.getNextNode(i);
                    } else {
                        break;
                    }
                }
            }
        }
        return null;
    }

    static final class Node<E> {
        E value;
        int level;
        Node<E>[] nextNode;

        public Node(E value, int level) {
            this.value = value;
            this.level = level;
            this.nextNode = new Node[level + 1];
        }

        public E getValue() {
            return value;
        }

        public void setValue(E value) {
            this.value = value;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }

        public Node<E> getNextNode(int level) {
            return this.nextNode[level];
        }

        public void setNextNode(int level, Node<E> node) {
            this.nextNode[level] = node;
        }

    }

}
